Abstract:

We consider a hypothesis selection problem: given samples from an unknown probability distribution P and a set of m probability distributions H, the goal is to output a distribution from H whose distance to P is competitive with the best such distribution. This problem is well studied in the classical setting, with effective methods for this problem proposed and developed by Yatracos, and Devroye and Lugosi. This important primitive is surprisingly flexible, and provides easy and user friendly tools for converting a cover to a learner for distribution classes.

We revisit this task under the constraint of differential privacy in both the local and central models, demonstrating qualitative similarities and differences with the non-private setting. These allow us to easily derive algorithms for many classes with near-optimal sample complexity, in some cases defying conventional beliefs on the behaviour. Connections to other problems, including parallel maximum selection, will also be discussed.

No knowledge of differential privacy will be assumed. Based on joint works with Mark Bun, Thomas Steinke, and Zhiwei Steven Wu (https://arxiv.org/abs/1905.13229, NeurIPS '19), and Sivakanth Gopi, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, and Huanyu Zhang (https://arxiv.org/abs/2002.09465, COLT '20).